COMMENT ⊗   VALID 00005 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	.require "memo.pub[let,jmc]" source
C00019 00003	References:
C00020 00004	Notes for talk May 14
C00023 00005	Using approximately the formalism of
C00025 ENDMK
C⊗;
.require "memo.pub[let,jmc]" source
.cb MORE ON NON-MONOTONIC REASONING

.cb John McCarthy


	These notes supplement (McCarthy 1980).

	#. Section 7 - More on Blocks - axiomatizes the conditions for
moving one block onto another.  That formalization reifies (introduces
as individuals of the domain) "things" that may prevent the action.
This reification is unnecessary (though it may be useful), and
we get a somewhat neater formulation by replacing equation (22) of
that section by

!!a1:	%2∀x y s.(doable(move(x,y),s) ⊃ on(x,y,result(move(x,y),s)))%1,

which combines all the conditions for performing an action
into the notion that the action is ⊗doable in a situation.
We can write a general statement that an action has its normal
consequence provided it is doable in the form

!!a2:	%2∀action s.(doable(action,s) ⊃ conseq(action,result(action,s)))%1

and specialize it to the case at hand by writing

!!a3:	%2∀x y s'.(conseq(move(x,y),s') ≡ on(x,y,s'))%1.

Actually we might write

!!a3a:	%2∀x y s'.(conseq(move(x,y),s') ⊃ on(x,y,s'))%1

and get ({eq a3}) by circumscription.  Perhaps many frame
arise this way.

	We further have

!!a4:	%2∀x y s.(tooheavy(x,s) ⊃ ¬doable(move(x,y),s))%1

and

!!a5:	%2∀x y s.(¬clear(y,s) ⊃ ¬doable(move(x,y),s))%1.

Circumscribing ⊗¬doable in ({eq a4})∧({eq a5}) gives

!!a6:	%2∀x y s.(doable(move(x,y),s) ≡ ¬tooheavy(x,s) ∧ clear(y,s))%1.

The axioms for actions usually given in AI formulations can be
regarded as obtained by this kind of circumscription from the
more open-ended subjective formulations of common sense knowledge
whose listings of what can prevent an action are subjectively
recognized to be incomplete.
The circumscriptions have been done naively researchers who
write axioms giving sufficient conditions for actions.

	This is still insufficient reification to permit statements
about when one should circumscribe.

	#. What are the reasoning processes that go to the Amarel
representation of M and C or to a similarly simple representation
of a concrete set of blocks on a table?  The model should be
somehow "constructible" by the reasoning program once we have
decided what facts to take into account.  A crucial step seems
to be the mental act

	"Let the triplet (m,c,b) be the numbers of missionaries,
cannibals and boats on the initial bank of the river in a given
situation".

	#. What is the relation between circumscription and principles of
simplicity and Ockham's razor and all of these to %2ceteris paribus%1?

	#. Circumscriptions are made by minimizing predicates.
Are there corresponding rules for generating Reiter
or McDermott-Doyle defaults?

	#. More on the propositional case.

	It is informative to consider the general form of a
circumscription of a propositional letter ⊗p in an axiom ⊗A.  We
can always write ⊗A in the form (essentially disjunctive normal form)

!!a7:	%2(a1 ⊃ p) ∧ (a2 ⊃ ¬p)%1

where ⊗a1 and ⊗a2 involve other propositional variables.  The
circumscription is simply

	%2p ≡ a1%1.

Suppose there is another free variable ⊗q, and we want to adjust ⊗q so
as to make ⊗p as false as possible.  Then the axiom takes the form

	%2(a1∧q ∨ a2∧¬q ⊃ p) ∧ (a3∧q ∨ a4∧¬q ⊃ ¬p)%1,

and the result of circumscription is

	%2p ≡ a1∧a2%1.

	The next simplest case is when ⊗p(x) is a unary predicate.
It isn't yet clear whether the occurences of clauses
like

	%2p(x) ∧ ¬p(y)%1

give trouble for circumscription - i.e. results not in accordance
with intuition.

	As for examples, there seems to be no problem about obtaining
the usual S-expression partial ordering by circumscribing < in
the axiom

	%2∀xy.(x < x.y ∧ y < x.y) ∧ ∀xyz.(x < y ∧ y < z ⊃ x < z)%1

Looking at it from another point of view, we get the axiom schema of
LISP induction.

Second thought: Actually there may be a problem in getting the ordering.

Third thought: There is no problem.  We need only plug in the usual
recursive definition of the ordering and show that it satisfies the
schema.

Fourth thought: But how do we show that it is minimal?

Fifth thought: It looks like the  minimization schema
for the program will show that it satisfies the circumscription
schema.

	#. The axiom

!!a9:	%2∀x ∃y.(y > x) ∧ P(y))%1

leads to a contradictory circumscription assuming that the ordering is
irreflexive.  This is because any predicate ⊗P satisfying ({eq a9}) will
be true for an infinite unbounded set of elements of the domain, but it
can be made false at any subset and remain a solution provided what
remains is unbounded.  Thus there is no minimal solution.  This is
probably the paradigm example.

	#. Bayesian reasoning is intrinsically non-monotonic.
Statements of probabilities including conditional probabilities
are supplemented by statements of the outcomes of experiments.
This gives new values for the %2a posteriori%1 probabilities.

	#. Sometimes one makes the default assumption that a quantity
only depends on certain others or perhaps that it depends only on what
it is explicitly stated to depend on.  Sometimes this might be formalized
by asserting that a certain function is of two arguments rather than
three or more.  This won't be so easy.

	#. Another default is that entities with different names are
different.  This is the first where the syntactic form of what is
stated must be taken into account and should serve as a prototype
before dealing with more precise discourse bound defaults.
We can limit the extent to which we must formalize the syntax by supposing
that objects have names and postulating

	%2∀x y.ifposs[x ≠ y ⊃ denotation x ≠ denotation y]%1

or

	%2∀x y u v.ifposs[names(x,u) ∧ names(y,v) ∧ x ≠ y ⊃ u ≠ v]%1,

where ⊗ifposs[<sentence>] abbreviates %2M <sentence> ⊃ <sentence>%1.
We assume that names are expressions, and we can test their equality
directly.
Of course, this also limits what we get out of formalizing the syntax.


	#. In general, the schema of circumscription cannot be replaced
by any finite collection of sentences.  This is a consequence of the
fact, proved by mathematicians, that the axiom schema of induction (a
special case of circumscription) cannot be replaced by a finite collection
of axioms.  However, when there aren't functions giving rise to an
infinite domain, it would seem plausible that the schema of circumscription
could be replaced by a finite formula - perhaps a finite conjunction
of instances of the schema.

	Perhaps the right instance has the form

	%2qF(x,y) ≡ x=tx1 ∧ y=ty1 ∨ x=tx2 ∧ y=ty2 ∨ ...%1

where ⊗tx1, etc are terms composed from constants and functions.  In
general the disjunction would be infinite, but in case the functions
don't generate an infinite set, the disjunction is finite.  In this
case circumscription might give something like a closed world assumption.

	#. Perhaps the methods that Boyer and Moore apply to determining
the right instances of LISP induction schemata can be applied to
determining the right instances of circumscription - at least when
the goal is to prove a specific formula.

	#. Many conjectures that I kill with circumscription are popularly
killed by the non-monotonic heuristic
%2"If that were true, I would know it"%1, which we abbreviate IWKI.
Thus Nilsson
mentions "If Henry Kissinger were nine feet tall, I would know it".
This one is certainly disposable by circumscription, i.e. if the
height of Kissinger is in question and we circumscribe the available
information, we will get that it is ordinary.  However, IWKI permits
greater confidence that we have not merely accidentally missed the
fact that Kissinger is nine feet tall.  On the other hand, circumscription
is logically simpler, since it doesn't require reasoning about knowledge.
Indeed application of IWKI may involve a circumscription.  The relations
between these non-monotonic reasoning methods need to be clarified.

	#. The derivation of non-knowledge is presumably a circumscription
and needs to be re-examined.

	#. The study of formalization began at the beginning of
this century with the idea that we would start with the facts
about the world, express them as sentences in a logical language,
and then build the theory by deduction.  Later it was proposed
to start from the sentences as axioms and consider sets of facts
compatible with the axioms, i.e. study models of the axioms.
Consider starting with the set of facts and imagining that they
can be expressed in a variety of languages.  We must imagine that
the predicate names are not even given.  Thus suppose we want to
say that Newton and Leibniz both invented calculus.  There is
no reason to suppose that they used the same terminology, and
they didn't.  More prosaically, when we say that Pat and Mike both
know about carburetors, we don't presume a particular language for
expressing facts about carburetors, and we may not know any such
language.  This has to do with "knowing about".
References:

%3McCarthy, John (1980)%1: 
"Circumscription - A Form of Non-Monotonic Reasoning", %2Artificial
Intelligence%1, Volume 13, Numbers 1,2, April.

%3Reiter, Raymond (1979): "On Reasoning by Default" in %2TINLAP II%1 an
and also %2American Journal of Computational Linguistics%1, 1979,
Microfiche 80.

vague[e80,jmc] 23-aug-80	How to formalize vague concepts
Notes for talk May 14

1. Why non-monotonic reasoning and why it can be discussed
epistemologically.  Why we say "non-monotonic reasoning" rather
than "non-monotonic logic".

I will let you feel the trunk and one ear of the elephant.

defeasible presumptions

[unsafe because there may be a train]

circumscribing what objects exist

Avoiding making distinctions till they are necessary
Necessary if philosophy is to be realistic and AI is to be possible.

2. Examples
	[noon ∧ M sunny ⊃ sunny] ∧ noon ∧ [eclipse ⊃ not sunny]
	the meeting will be on Wednesday unless there is reason to do different
	the story of the peas
	isflier tweety
	M istrain ⊃ unsafe
	non ex boats and helicopters
	Mary's home town - the cases where it isn't well defined
must be treated in an ad hoc way
	attempting to bribe a public official
		a. didn't know he was an official
		b. mistakenly thought he was an official
		c. advertised for a bribee
It would be desirable to have a purely de re example where a distinction
is not imagined until the necessity for it arises.  Zenon suggests
"mammal" but here we can suppose that the ambiguities are known in
advance.  Best one in which the audience doesn't see the ambiguity
till it is pointed out.

3. Formalisms
	McDermott, Reiter, McCarthy
	Davis and Stalnaker comments
	Weyhrauch and Winograd

4. Heuristic aspects of non-monotonic reasoning
	refer to Reiter, microplanner, Doyle, and Moore

5. The problem of formalizing "natural kinds".
Using approximately the formalism of
CONCEP[E76,JMC]
we can write

¬unextensional(f) ∧ value x = value y ⊃ value f(x) = value f(y)

and circumscribe ⊗unextensional, i.e. we say that a function is
extensional unless there is evidence to the contrary.

	There are two ways of looking at circumscription.  Mostly I
have regarded it as a rule of conjecture that may be chosen for local
reasons at some point in a thinking process.  The other way corresponds
to defaults; namely, we are always ready to circumscribe a certain
predicate like the above ⊗unextensional.  We need additional language
in order to express such a default - analogous to that of
McDermott-Doyle or Reiter.

This file is circum.mor[s80,jmc], and this version was pubbed on {date}.